perm filename NBS.NOT[NBS,WD]1 blob
sn#203701 filedate 1976-04-17 generic text, type T, neo UTF8
The Initial Permutation
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
The initial permutation can easily be seen to have been formed as
follows. The numbers 1 through 64 were written from top to bottom and from
right to left in a square array eight elements on a side. The even rows were
then separated out and placed above the odd. The result is then read off from
left to right and from top to bottom.
IP may be decomposed into cycles as follows:
(1 58 55 13 28 40)
(2 50 53 29 32 8)
(3 42 51 45 27 48)
(4 34 49 61 31 16)
(5 26 56)
(6 18 54 21 30 24)
(7 10 52 37 25 64)
(9 60 39)
(11 4435 41 59 47)
(12 36 33 57 63 15)
(14 20 38 17 62 23)
(19 46)
(22)
These are the selection functions S1...S8 of the NBS algorithm, which
map 6 bit quantities to four bit ones. The image of a six bit number is
obtained by taking the first and last bits as the row number in one of the
following tables, and the middle four bits as the column number.
Note that each row is a permutation of the numbers 0...15.
S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
Each row of an S is a permutation of the numbers 0 through 15 and
may be written as a product of cycles.
S1
Row 1: (0 14) (1 4 2 13 9 10 6 11 12 5 15 7 8 3)
Row 2: (0) (1 15 8 10 12 9 6 13 5 2 7) (3 4 14)
Row 3: (0 4 13 10 9 12 3 8 15) (1) (2 14 5 6) (7 11)
Row 4: (0 15 13) (1 12 10 3 2 8 5 9 11 14 6) (4) (7)
S2
(0 15 10 2 8 9 7 4 6 3 14 5 11 13) (1) (12)
(0 3 7 14 11 10 1 13 9) (2 4 15 5) (6 8 12)
(0) (1 14 2 7) (3 11 6 13) (4 10 12 9 8 5) (15)
(0 13 5 15 9 6 4 3 18 11 12) (2 10 7) (14)
S3
(0 10 12 11 7 5 3 14 2 9 13 4 6 15 8 1)
(0 13 11 14 15 1 7 10 5 4 3 9 8 2)
(0 13 10 2 4 8 11 12 5 15 7) (1 6 3 9) (14)
(0 1 10 14 2 13 5 9 15 12 11 3) (4 6 8) (7)
S4
(0 7 10 8 1 13 12 11 5 6 9 2 14 4) (3) (15)
(0 13 10 2 11 12 1 8 4 6) (3 5 15 9 7) (14)
(0 10 3) (1 6 7 13 2 9) (4 12 5 11 14 8 15)
(0 3 6 13 7 8 9 4 10 5 1 15 14 2) (11) (12)
S5
(0 2 4 7 6 11 15 9 5 10 3 1 12 13) (8) (14)
(0 14 8 5 7 1 11 10 15 6 13 9) (2) (3 12) (4)
(0 4 10 12 6 7 8 15 14) (1 2) (3 11 5 13) (9)
(0 11 9 15 3 7 13 4 1 8 6 2 12 19) (5 14)
S6
(0 12 14 5 2 10 3 15 11 4 9 13 7 8) (1) (6)
(0 10 13 11 14 3 2 4 7 5 12) (1 15 8 6 9)
(0 9) (1 14 11 10 4 2 15 6 12) (3 5 8 7) (13)
(0 4 9 14 8 11 7 10 1 3 12 6 15 13) (2) (5)
S7
(0 4 15 1 11 7 13 10 9 12 5) (2) (3 14 6 8)
(0 13 15 6 1) (2 11 12) (3 7 10 5 9) (4) (8 14)
(0 1 4 12) (2 11 8 10 6 7 14 9 15) (3 13 5)
(0 6 10) (1 11 15 12 14 3 8 9 5 4) (2 13) (7)
S8
(0 13) (1 2 8 10 3 4 6 11 14 12 5 15 7) (9)
(0 1 15 2 13 14 9 5 3 8 12) (4 10 6 7) (11)
(0 7 2 4 9 6 14 5 12 15 8) (1 11 13 3) (10)
(0 2 14 6 8 15 11) (1) (3 7 13 5 10 9 12) (4)
The process which decomposes a six bit number by taking the first and
last bits to represent a row and the middle bits to represent a column, results
in elements being chosen from the any of the S tables in the following order.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32
2 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63
3 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64
P
16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25
Written as a product of cycles, P becomes:
(1 16 10 15 31 4 21 32 25 19 24 9)
(2 7 28 6 12 26 13 5 29 22 27 30 11 23 3 20 14 18 8 17)
Permuted Choice 1
The structure of permuted choice 1 is more clearly visible
when it is presented in 8 columns rather than 7. The division into
two parts is maintained. Each half has four and one half rows of
length eight.
57 49 41 33 25 17 9 1
58 50 42 34 26 18 10 2
59 51 43 35 27 19 11 3
60 52 44 36
63 55 47 39 31 23 15 7
62 54 46 38 30 22 14 6
61 53 45 37 29 21 13 5
28 20 12 4
As the bits 8, 16, 24, 32, 40, 48, 56, and 64 are not used,
things bocome even clearer if the bits are renumbered from 1 to 56.
The above array then becomes:
50 43 36 29 22 15 8 1
51 44 37 30 23 16 9 2
52 45 38 31 24 17 10 3
53 46 39 32
56 49 42 35 28 21 14 7
55 48 41 34 27 20 13 6
54 47 40 33 26 19 12 5
25 18 11 4
The permutation is now clear. Turn the lower group upside
down and slide the short row to the right, to get:
50 43 36 29 22 15 8 1
51 44 37 30 23 16 9 2
52 45 38 31 24 17 10 3
53 46 39 32
25 18 11 4
54 47 40 33 26 19 12 5
55 48 41 34 27 20 13 6
56 49 42 35 28 21 14 7
The two parts can now be assembled into a rectangle written from top
to bottom and right to left.
K1 through K16 are the 48 bit subsets of the 64 bit key
employed in each of the 16 rounds of the NBS cipher. They are
organized in six rows of eight columns, read across then down.
K1
26 2 50 11 36 33 49 44
18 25 35 58 19 51 42 41
60 9 10 17 52 43 34 57
38 13 55 7 53 20 63 46
21 6 39 45 14 37 54 12
31 5 61 30 29 15 4 47
K2
34 10 58 19 44 41 57 52
26 33 43 1 27 59 50 49
3 17 18 25 60 51 42 36
46 21 63 15 61 28 4 54
29 14 47 53 22 45 62 20
39 13 6 38 37 23 12 55
K3
50 26 9 35 60 57 44 3
42 49 59 17 43 10 1 36
19 33 34 41 11 2 58 52
62 37 12 31 14 13 20 7
45 30 63 6 38 61 15 5
55 29 22 54 53 39 28 4
K4
1 42 25 51 11 44 60 19
58 36 10 33 59 26 17 52
35 49 50 57 27 18 9 3
15 53 28 47 30 29 5 23
61 46 12 22 54 14 31 21
4 45 38 7 6 55 13 20
K5
17 58 41 2 27 60 11 35
9 52 26 49 10 42 33 3
51 36 1 44 43 34 25 19
31 6 13 63 46 45 21 39
14 62 28 38 7 30 47 37
20 61 54 23 22 4 29 5
K6
33 9 57 18 43 11 27 51
25 3 42 36 26 58 49 19
2 52 17 60 59 50 41 35
47 22 29 12 62 61 37 55
30 15 13 54 23 46 63 53
5 14 7 39 38 20 45 21
K7
49 25 44 34 59 27 43 2
41 19 58 52 42 9 36 35
18 3 33 11 10 1 57 51
63 38 45 28 15 14 53 4
46 31 29 7 39 62 12 6
21 30 23 55 54 5 61 37
K8
36 41 60 50 10 43 59 18
57 35 9 3 58 25 52 51
34 19 49 27 26 17 44 2
12 54 61 13 31 30 6 20
62 47 45 23 55 15 28 22
37 46 39 4 7 21 14 53
K9
44 49 3 58 18 51 2 26
36 43 17 11 1 33 60 59
42 27 57 35 34 25 52 10
20 62 6 21 39 38 14 28
7 55 53 31 63 23 5 30
45 54 47 12 15 29 22 61
K10
60 36 19 9 34 2 18 42
52 59 33 27 17 49 11 10
58 43 44 51 50 41 3 26
5 15 22 37 55 54 30 13
23 4 6 47 12 39 21 46
61 7 63 28 31 45 38 14
K11
11 52 35 25 50 18 34 58
3 10 49 43 33 36 27 26
9 59 60 2 1 57 19 42
21 31 38 53 4 7 46 29
39 20 22 63 28 55 37 62
14 23 12 13 47 61 54 30
K12
27 3 51 41 1 34 50 9
19 26 36 59 49 52 43 42
25 10 11 18 17 44 35 58
37 47 54 6 20 23 62 45
55 5 38 12 13 4 53 15
30 39 28 29 63 14 7 46
K13
43 19 2 57 17 50 1 25
35 42 52 10 36 3 59 58
41 26 27 34 33 60 51 9
53 63 7 22 5 39 15 61
4 21 54 28 29 20 6 31
46 55 13 45 12 30 23 62
K14
59 35 18 44 33 1 17 41
51 58 3 26 52 19 10 9
57 42 43 50 49 11 2 25
6 12 23 38 21 55 31 14
20 37 7 13 45 5 22 47
62 4 29 61 28 46 39 15
K15
10 51 34 60 49 17 33 57
2 9 19 42 3 35 26 25
44 58 59 1 36 27 18 41
22 28 39 54 37 4 47 30
5 53 23 29 61 21 38 63
15 20 45 14 13 62 55 31
K16
18 59 42 3 57 25 41 36
10 17 27 50 11 43 34 33
52 1 2 9 44 35 26 49
30 5 47 62 45 12 55 38
13 61 31 37 6 29 46 4
23 28 53 22 21 7 63 39
The following are the bits omitted in each of K1 through K16, by the
reduction from 56 to 48 bits.
K1: 1 3 8 16 22 23 24 27 28 32 40 48 56 59 62 64
K2: 2 5 7 8 9 11 16 24 30 31 32 35 40 48 56 64
K3: 8 16 18 21 23 24 25 27 32 40 46 47 48 51 56 64
K4: 2 8 16 24 32 34 37 39 40 41 43 48 56 62 63 64
K5: 8 12 15 16 18 24 32 40 48 50 53 55 56 57 59 64
K6: 1 4 6 8 10 16 24 28 31 32 34 40 44 48 56 64
K7: 8 13 16 17 20 22 24 26 32 40 47 48 50 56 60 64
K8: 1 5 8 11 16 24 29 32 33 38 40 42 48 56 63 64
K9: 4 8 9 13 16 19 24 32 37 40 41 46 48 50 56 64
K10: 1 8 16 20 24 25 29 32 35 40 48 53 56 57 62 64
K11: 5 6 8 15 16 17 24 32 40 41 44 45 48 51 56 64
K12: 2 8 16 21 22 24 31 32 33 40 48 56 57 60 61 64
K13: 8 11 14 16 18 24 32 37 38 40 44 47 48 49 56 64
K14: 8 16 24 27 30 32 34 36 40 48 53 54 56 60 63 64
K15: 6 7 8 11 12 16 24 32 40 43 46 48 50 52 56 64
K16: 8 14 15 16 19 20 24 32 40 48 51 54 56 58 60 64
K1 through K16 are the 48 bit subsets of the 64 bit key employed in each
of the 16 rounds of the NBS cipher, renumbered from 1 to 56 by omitting the bits
8, 16, 24, 32, 40, 48, 56, and 64, which are never used. They are organized in
six rows of eight columns, read across then down.
K1
23 2 44 10 32 29 43 39
16 22 31 51 17 45 37 36
53 8 9 15 46 38 30 50
34 12 49 7 47 18 56 41
19 6 35 40 13 33 48 11
28 5 54 27 26 14 4 42
K2
30 9 51 17 39 36 50 46
23 29 38 1 24 52 44 43
3 15 16 22 53 45 37 32
41 19 56 14 54 25 4 48
26 13 42 47 20 40 55 18
35 12 6 34 33 21 11 49
K3
44 23 8 31 53 50 39 3
37 43 52 15 38 9 1 32
17 29 30 36 10 2 51 46
55 33 11 28 13 12 18 7
40 27 56 6 34 54 14 5
49 26 20 48 47 35 25 4
K4
1 37 22 45 10 39 53 17
51 32 9 29 52 23 15 46
31 43 44 50 24 16 8 3
14 47 25 42 27 26 5 21
54 41 11 20 48 13 28 19
4 40 34 7 6 49 12 18
K5
15 51 36 2 24 53 10 31
8 46 23 43 9 37 29 3
45 32 1 39 38 30 22 17
28 6 12 56 41 40 19 35
13 55 25 34 7 27 42 33
18 54 48 21 20 4 26 5
K6
29 8 50 16 38 10 24 45
22 3 37 32 23 51 43 17
2 46 15 53 52 44 36 31
42 20 26 11 55 54 33 49
27 14 12 48 21 41 56 47
5 13 7 35 34 18 40 19
K7
43 22 39 30 52 24 38 2
36 17 51 46 37 8 32 31
16 3 29 10 9 1 50 45
56 34 40 25 14 13 47 4
41 28 26 7 35 55 11 6
19 27 21 49 48 5 54 33
K8
32 36 53 44 9 38 52 16
50 31 8 3 51 22 46 45
30 17 43 24 23 15 39 2
11 48 54 12 28 27 6 18
55 42 40 21 49 14 25 20
33 41 35 4 7 19 13 47
K9
39 43 3 51 16 45 2 23
32 38 15 10 1 29 53 52
37 24 50 31 30 22 46 9
18 55 6 19 35 34 13 25
7 49 47 28 56 21 5 27
40 48 42 11 14 26 20 54
K10
53 32 17 8 30 2 16 37
46 52 29 24 15 43 10 9
51 38 39 45 44 36 3 23
5 14 20 33 49 48 27 12
21 4 6 42 11 35 19 41
54 7 56 25 28 40 34 13
K11
10 46 31 22 44 16 30 51
3 9 43 38 29 32 24 23
8 52 53 2 1 50 17 37
19 28 34 47 4 7 41 26
35 18 20 56 25 49 33 55
13 21 11 12 42 54 48 27
K12
24 3 45 36 1 30 44 8
17 23 32 52 43 46 38 37
22 9 10 16 15 39 31 51
33 42 48 6 18 21 55 40
49 5 34 11 12 4 47 14
27 35 25 26 56 13 7 41
K13
38 17 2 50 15 44 1 22
31 37 46 9 32 3 52 51
36 23 24 30 29 53 45 8
47 56 7 20 5 35 14 54
4 19 48 25 26 18 6 28
41 49 12 40 11 27 21 55
K14
52 31 16 39 29 1 15 36
45 51 3 23 46 17 9 8
50 37 38 44 43 10 2 22
6 11 21 34 19 49 28 13
18 33 7 12 40 5 20 42
55 4 26 54 25 41 35 14
K15
9 45 30 53 43 15 29 50
2 8 17 37 3 31 23 22
39 51 52 1 32 24 16 36
20 25 35 48 33 4 42 27
5 47 21 26 54 19 34 56
14 18 40 13 12 55 49 28
K16
16 52 37 3 50 22 36 32
9 15 24 44 10 38 30 29
46 1 2 8 39 31 23 43
27 5 42 55 40 11 49 34
12 54 28 33 6 26 41 4
21 25 47 20 19 7 56 35
The following are the bits omitted in each of K1 through K16, by the
reduction from 56 to 48 bits.
K1: 1 3 20 21 24 25 52 55
K2: 2 5 7 8 10 27 28 31
K3: 16 19 21 22 24 41 42 45
K4: 2 30 33 35 36 38 55 56
K5: 11 14 16 44 47 49 50 52
K6: 1 4 6 9 25 28 30 39
K7: 12 15 18 20 23 42 44 53
K8: 1 5 10 26 29 34 37 56
K9: 4 8 12 17 33 36 41 44
K10: 1 18 22 26 31 47 50 55
K11: 5 6 14 15 36 39 40 45
K12: 2 19 20 28 29 50 53 54
K13: 10 13 16 33 34 39 42 43
K14: 24 27 30 32 47 48 53 56
K15: 6 7 10 11 38 41 44 46
K16: 13 14 17 18 45 48 51 53
PC2
14 17 11 24 1 5 3 28
15 6 21 10 23 19 12 4
26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40
51 45 33 48 44 49 39 56
34 53 46 42 50 36 29 32
Notice that the first 24 elements are selected entirely from the inputs
between 1 an 28 while the latter 24 are take entirely from those between 29 and
56.
The elements omitted are: 9, 18, 22, 25, 35, 38, 43, and 54. These are
taken equally from the two halves.